package cn.edu.jxau.test;

/**
 * 求链表的长度,考虑有环的情况
 * 
 * @author Fudashi
 */
public class Main {

	public static void main(String[] args) {

		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7);
		Node node8 = new Node(8);
		Node node9 = new Node(8);
		Node node10 = new Node(10);
		Node node11 = new Node(11);
		Node node12 = new Node(12);
		Node node13 = new Node(13);
		node1.next = node2;
		node2.next = node3;
		node5.next = node6;
		node6.next = node7;
		Node cur = merge(node1, node5);
		while (cur != null) {
			System.out.print(cur.data + " ");
			cur = cur.next;
		}
	}

	/**
	 * 两个链表不能交叉
	 * @param first1
	 * @param first2
	 * @return
	 */
	public static Node merge(Node first1, Node first2) {

		if (first1 == null && first2 == null) {
			return null;
		} else if (first1 == null) {
			return first2;
		} else if (first2 == null) {
			return first1;
		}
		Node head = new Node();
		Node cur = head;
		// 1.merge //
		Node c1 = first1;
		Node c2 = first2;
		while (c1 != null && c2 != null) {
			if (c1.data < c2.data) {
				Node next = c1.next;
				c1.next = null;
				cur.next = c1;
				cur = cur.next;
				c1 = next;
			} else {
				Node next = c2.next;
				c2.next = null;
				cur.next = c2;
				cur = cur.next;
				c2 = next;
			}
		}
		System.out.println(c1 + "	" + c2);
		if (c1 != null) { // first1链表未完全归并
			cur.next = c1;
		}
		if (c2 != null) { // first2链表未完全归并
			cur.next = c2;
		}
		return head.next;
	}
}

class Node {

	public int data;
	public Node next;

	public Node() {

	}

	public Node(int data) {
		this.data = data;
	}
}

//------------------------------
// 递归解法
//------------------------------

package cn.edu.jxau.test;

/**
 * 求链表的长度,考虑有环的情况
 * 
 * @author Fudashi
 */
public class Main {

	public static void main(String[] args) {

		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7);
		Node node8 = new Node(8);
		Node node9 = new Node(8);
		Node node10 = new Node(10);
		Node node11 = new Node(11);
		Node node12 = new Node(12);
		Node node13 = new Node(13);
		node1.next = node2;
		node2.next = node3;
		node5.next = node6;
		node6.next = node7;
		Node cur = merge(node1, node5);
		while (cur != null) {
			System.out.print(cur.data + " ");
			cur = cur.next;
		}
	}

	public static Node merge(Node first1, Node first2) {
		if (first1 == null && first2 == null) {
			return null;
		}
		return merge0(first1, first2);
	}

	/**
	 * 两个链表不能交叉
	 * 
	 * @param first1
	 * @param first2
	 * @return
	 */
	public static Node merge0(Node first1, Node first2) {

		if (first1 == null) {
			return first2;
		}
		if (first2 == null) {
			return first1;
		}
		Node head = null;
		if (first1.data < first2.data) {
			head = first1;
			head.next = merge0(first1.next, first2);
		} else {
			head = first2;
			head.next = merge0(first1, first2.next);
		}
		return head;
	}
}

class Node {

	public int data;
	public Node next;

	public Node() {

	}

	public Node(int data) {
		this.data = data;
	}
}